1. Field of the Invention
This invention pertains generally to microcomputer instruction sets. More particularly, the invention is a method and apparatus for computing leading zero count with offset using a parallel nibble calculation scheme.
2. The Prior Art
In certain microcomputer instruction sets such as the MAJC (Micro Architecture for Java Computing) architecture by Sun Microsystems(copyright), a leading zero count with offset instruction is carried out. For example, when evaluation of the saturation of a fixed-length word is desired, the leading zero count with offset instruction provides the number of significant bits, allowing for an offset.
Leading zero count with offset (LZCO) instruction comprises counting the number of leading zeros in a first number and subtracting a second xe2x80x9coffsetxe2x80x9d number from this count value. FIG. 1 shows a LZCO instruction implementation 1 according to the prior art.
As noted above, in LZCO instruction, two input operands, identified as RS1 (designated 2) and RS2 (designated as 3), are provided. By way of example, RS1 is depicted as a 32-bit number and RS2 is depicted as a 5-bit number. The count of leading zeros in RS1 must be determined. RS2 provides the xe2x80x9coffsetxe2x80x9d value with is subtracted from the count of leading zeros (determined from RS1).
The count of leading zeroes in RS1 is determined by a conventional leading zero detector (LZD) 4. The LZD 4 comprises software and/or circuitry to evaluate RS1 and determine the count of leading zeros in RS1 (designated as 5). This count 5 is provided as an output from LZD 4 and in provided as a first input for the subtrator unit 6.
The subtractor unit 6 has as its second input the RS2 offset 3. The subtractor unit 6 subtracts the RS2 value 3 from the count of leading zeros (5) to generate a 6-bit number result (7).
It is desirable to provide an implementation which carries out this LZCO operation in a fast manner. The prior art algorithm, while providing the correct result (7), is carried out in a relatively slow manner because the LZD must complete its function before the subtraction can begin. These operations are carried out serially, maximizing the delay for the result.
Accordingly, there is a need for a method and apparatus which provides for faster calculation of leading zero count with offset instruction. The present invention satisfies these needs, as well as others, via a parallel nibble calculation scheme and generally overcomes the deficiencies found in the background art.
The present invention is a method and apparatus for calculating leading zero count with offset (LZCO) instructions using a parallel nibble calculation scheme. The invention further relates to machine readable media on which are stored embodiments of the present invention. It is contemplated that any media suitable for retrieving instructions is within the scope of the present invention. By way of example, such media may take the form of magnetic, optical, or semiconductor media. The invention also relates to data structures that contain embodiments of the present invention, and to the transmission of data structures containing embodiments of the present invention.
The invention operates upon two input operands, identified as RS1 and RS2. RS1 is represented by a plurality of nibbles, each nibble comprising four bits. For example, if RS1 comprises a thirty-two (32) bit number, RS1 is represented by eight (8) nibbles. Each nibble has a corresponding nibble placement within RS1 corresponding to a relative nibble order of significance. For example, in the 32-bit RS1 example, Nibble 7 corresponds to bits 31, 30, 29, and 28 of RS1, Nibble 6 corresponds to bits 27, 26, 25, and 24, Nibble 5 corresponds to bits 23, 22, 21 and 20, and Nibble 0 corresponds to bits 3, 2, 1 and 0. As will be readily apparent to those skilled in the art, each of the other nibbles 1, 2, 3, and 4 corresponds to bits associated with the nibble""s placement within RS1.
Each nibble has a corresponding relative nibble order of significance, such that nibbles having higher bits will have a higher order of significance than nibbles having lower bits. For example, Nibble 7 comprising bits 31, 30, 29, and 28 will have a higher order of significance than Nibble 6 corresponding to bits 27, 26, 25 and 24 since bits 31, 30, 29, and 28 have a higher order of significance than bits 27, 26, 25 and 24. Accordingly, Nibble n will have a higher order of significance than Nibble (nxe2x88x921).
The RS2 operand is provided as an xe2x80x9coffsetxe2x80x9d value. As noted above, the desired result of the LZCO operation produces is a value of RS2 subtracted from the count of leading zeros in RS1. The present invention provides a parallel nibble calculation scheme to generate this result, as described herein.
According to a first embodiment of the invention, the method comprises calculating the lower two bits of the result for each nibble while simultaneously (or in parallel) calculating the upper remaining bits of the result for each nibble, and selecting the resulting nibble calculation for the lower two bits and the upper bits according to the nibble that corresponds to the highest order nibble without all zero values.
According to a second embodiment of the invention, the apparatus comprises a select circuit which receives as its input RS1 and produces an output; a lower two bits result calculator, having as its input RS1, RS2 and the select circuit output, the lower two bits result calculator providing an output; and an upper bit result calculator, having as its input RS2, the select circuit output, and the lower two bits result calculator output.
The output of the lower two bits result calculator provides the lower two bits of the desired LZCO operation result and a carryout value. The output of the upper bit result calculator provides the upper remaining bits of the desired LZCO operation result.
It will be apparent to those skilled in the art having the benefit of this disclosure that the invention is also suitable for calculating a leading ones count with offset using the parallel nibble calculation scheme of the present invention. Additionally, the invention is also suitable for calculation of leading zero/one count with an add offset, rather than a subtract offset with trivial modification to the embodiments as described herein as would be apparent to those skilled in the art. It is further noted that the present invention further provides a leading zero/one detector where the offset operand (RS2) is zero (0).
An object of the invention is to provide a method and apparatus for carrying out LZCO instruction which overcomes the deficiencies in the prior art.
Another object of the invention is to provide a method and apparatus for carrying out LZCO instruction which uses a parallel nibble calculation scheme.
Further objects and advantages of the invention will be brought out in the following portions of the specification, wherein the detailed description is for the purpose of fully disclosing the preferred embodiment of the invention without placing limitations thereon.